package com.heima.leetcode.datastructure.linkedlist;

/**
 * 有序链表去重，重复的节点一个不留
 */
public class DeleteAllDuplicates {

    /**
     * <h3>方法一，递归</h3>
     * 用递归实现链表去重，递的时候，如果当前递的节点的值等于下一次要递的节点的值，
     * 则下一次递跳过当前节点的下一个节点，
     * 进一步用while循环优化让递跳过一堆连续的与当前节点值相等的节点；
     * 如果当前递的节点的值不等于下一次要递的节点的值，
     * 则把当前递的节点加入到以下一个节点为头的链表的去重结果，
     * 又因为当前递的节点以前的递已经对当前节点以前的节点进行了去重，
     * 所以当前递的节点不可能是重复节点
     *
     * @param head 旧链表的头节点
     * @return 去重后的链表的头节点
     */
    public static ListNode deleteAllDuplicates1(ListNode head) {
        // 递的时候去掉重复元素，顺便处理一下特殊情况
        if (head == null || head.next == null) {
            return head;
        }
        // 头节点和第二个节点值相等，则返回第一次与头节点值不重复的节点为头的链表的去重结果
        if (head.val == head.next.val) {
            head = head.next;
            // 将head指针移到重复节点中的最后一个位置
            while (head.next != null) {
                if (head.val == head.next.val) {
                    head = head.next;
                    continue;
                }
                break;
            }
            // 返回重复节点中的最后一个位置之后的链表的去重结果
            return deleteAllDuplicates1(head.next);
        }
        // 头节点和第二个节点值不相等，head应当纳入以第二个节点为头节点的链表的去重结果中
        head.next = deleteAllDuplicates1(head.next);
        // 归的时候啥也不做
        return head;
    }

    /**
     * <h3>方法二，快慢指针法</h3>
     * 用三个指针分别记录重复节点中的第一个节点、第一个节点的前一个节点、最后一个节点的后一个节点
     * @param head 旧链表的头节点
     * @return 链表去重后的头节点
     */
    public static ListNode deleteAllDuplicates2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode sentinel = new ListNode(-1, head);
        ListNode p1 = sentinel; // p1用来记录重复节点中的第一个节点的前一个节点
        ListNode p2; // p2用来记录重复节点中的第一个节点
        ListNode p3; // p3用来记录重复节点的最后一个节点的下一个节点
        while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
            if (p2.val == p3.val) {
                // 删除重复节点
                while (p2.val == p3.val) {
                    p3 = p3.next;
                }
                p1.next = p3;
                // p2，p3 指针复位
            } else {
                // p1，p2，p3 往后移动一次
                p1 = p1.next;
            }
        }
        return sentinel.next;
    }
}
